package com.search;

import java.util.Arrays;

/**
 * @BelongsProject: DataStructures
 * @BelongsPackage: com.search
 * @Author: 江岸
 * @CreateTime: 2021-02-28 22:46
 * @Description: 斐波那契查找
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 6, 7, 9, 10, 16, 23,24,34 ,39, 108, 567, 900, 4561};
        System.out.println(fun(arr,39));
    }

    //[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
    public static int[] fib(int n){
        int[] ints = new int[n+1];
        ints[0] = 0;
        ints[1] = 1;
        for (int i=2;i<ints.length;i++){
            ints[i] = ints[i-1] + ints[i-2];
        }
        return ints;
    }

    public static int fun(int[] arr ,int target){
        int[] fib = fib(20);
        int newLenth = 0;
        int fibIndex = 0;
        //通过数组长度定位到斐波那契的数字
        while (arr.length>fib[fibIndex]){
            fibIndex++;
        }
        //数组长度为16，斐波那契数字为21
        newLenth = fib[fibIndex];
        int[] temp = Arrays.copyOf(arr, newLenth);
        //把数组最后一个数字扩充到新数组中
        for(int j=arr.length;j<temp.length;j++){
            temp[j] = arr[arr.length-1];
        }
        System.out.println(Arrays.toString(temp));
        int left = 0;
        //数列分割为 13+8=21 黄金点为 第13个数字 所以下标为mid
        int mid ;
        while (fibIndex>0){
             mid = left + fib[--fibIndex] - 1;
            if (temp[mid]<target){
                left=mid+1;
                fibIndex--;
            }else if(temp[mid]>target){
                //不做任何处理
            }else if(temp[mid]==target){
                return mid>=arr.length?arr.length-1:mid;
            }
        }
        return -1;
    }


}
